googologywikiaorg-20200223-history
Forum:How fast does this function grow?
Okay, define the F(x) as the largest finite number computed by any enumerating non-halting Turing Machine of X or less states. How would a NON-halting machine generate a LARGEST + FINITE number?Chronolegends (talk) 03:50, July 6, 2016 (UTC) The largest number it generates before it starts repeating in a predictable pattern :For this function to be well-defined you need to specify what you mean exactly by "repeating in a predictable pattern". Good luck finding a definition of that which makes all non-halting TMs repeat in a predictable pattern. LittlePeng9 (talk) 07:35, July 6, 2016 (UTC) :You could ask about how long it takes for configurations of a TM given blank input to become periodic (where a configuration is defined as head position, state, and tape). However, there are many non-halting TMs that do not end up periodic. -- ve 04:41, July 7, 2016 (UTC) :Are you sure? Because according to Wikipedia: :https://en.wikipedia.org/wiki/Halting_problem : A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state: ::...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine... (italics in original, Minsky 1967, p. 24) ::But Turing machines are not finite-state, since they have an infinite tape. Note that this is very important for the Busy Beaver function to be fast-growing, since a machine with at most n'' states will either halt within ''n steps or fall into an infinite repeating pattern, so the Busy Beaver number could not be all that big. Deedlit11 (talk) 06:16, July 7, 2016 (UTC) ::Be careful to distinguish states from configurations. Turing machines have finitely many states but infinitely many possible configurations. It is especially confusing that some authors call configurations "states" and states "control states." -- ve 15:11, July 7, 2016 (UTC) ::Well I actually got this idea from someone else, and he claimed that F(10,000,000,000) would be way greater than Rayo's Number :::That person is dead wrong. -- ve 21:10, July 7, 2016 (UTC) :::Hmmm.... F(x) is equal to BB(x). GoogleAarex2001 21:33, July 7, 2016 (UTC) :::No it isnt. BB(x) is the champion of *HALTING* TM's of x states, his F(x) is akin to saying "what is the largest finite number a machine that counts up could produce, before entering some repeating pattern" ie. doesn't exist.Chronolegends (talk) 22:55, July 7, 2016 (UTC) :::So there's no way to define this function? ::::In order to make this function well-defined, you have to define precisely what you mean by the largest number computed by a nonhalting machine. So far you haven't provided a satisfying definition, but it doesn't mean such a definition isn't possible (even though Chronolegends seems to claim one can't define it). Admittedly there is little hope you can define it so that it works for all nonhalting TMs, but feel free to try. LittlePeng9 (talk) 07:28, July 9, 2016 (UTC)